#ifndef CONNECTEDCOMPONENTS_H
#define CONNECTEDCOMPONENTS_H

#include <QtCore>

#include <igraph.h>

namespace sk {

class ConnectedComponents {
public:
    ConnectedComponents(CGraph* graph) : graph(graph), allocSz(graph->getVerticesCount()) {
        cc = new int[allocSz];
        visited = new bool[allocSz];
    }

    ~ConnectedComponents() {
        delete[] cc;
        delete[] visited;
    }

    void go() {
        memset(cc, -1, sizeof(cc)*allocSz);
        memset(visited, 0, sizeof(visited)*allocSz);

        c = 0;
        for (int i = 1; i < allocSz + 1; i++) {
            visit(i);
            c++;
        }
    }

private:
    void visit(int v) {
        if (visited[v]) return;

        cc[v] = c;
        visited[v] = 1;
        foreach (int s, graph->getAdjanancies(v)) {
            visit(s);
        }
    }

    CGraph* graph;
    int allocSz;
    int* cc;
    int c;
    bool* visited;
};


}

#endif // CONNECTEDCOMPONENTS_H
